package edu.uci.ics.ai.maze.models;

import edu.uci.ics.ai.maze.utils.MazeUtils;

/**
 * Fields in an Edge are unmodifiable.
 */
public class Edge implements Cloneable {

  private static final double SKEW_DEG = 0.1;

  /**
   * the start point of the edge
   */
  private final Vertex start;

  /**
   * the end point of the edge
   */
  private final Vertex end;
  
  public Edge(Vertex start, Vertex end) {
    this.start = start;
    this.end = end;
  }

  @Override
  public Object clone() throws CloneNotSupportedException {
    return super.clone();
  }

  /**
   * Returns a new enlarged Edge.
   * 
   * @param enLargeFactor
   * @return
   */
  public Edge enlarge(int enLargeFactor) {
    Vertex s = new Vertex(enLargeFactor * start.getX(), enLargeFactor * start.getY());
    s.setPolygon(start.getPolygon());
    Vertex e = new Vertex(enLargeFactor * end.getX(), enLargeFactor * end.getY());
    e.setPolygon(end.getPolygon());
    return new Edge(s, e);
  }

  /**
   * Returns the start point.
   *
   * @return
   */
  public Vertex getStart() {
    return start;
  }

  /**
   * Returns the end point.
   *
   * @return
   */
  public Vertex getEnd() {
    return end;
  }

  public Vertex getMidPoint() {
    Vertex v = new Vertex(
            start.getX() + (end.getX() - start.getX()) / 2,
            start.getY() + (end.getY() - start.getY()) / 2);
    return v;
  }

  public Edge getReverse() {
    return new Edge(this.end, this.start);
  }

  /**
   * Returns the length of this object Edge
   * @return
   */
  public double getLength() {
    return MazeUtils.euclideanDistance(start, end);
  }

  /**
   * Returns true if the provided edge intersects this edge?
   *
   * isIntersect receive an edge as its parameter and check to see whether
   * or not this pass-in edge will intersect the current object Edge in one
   * or the other ways.
   * @param pq
   * @param skew
   * @return true if intersect, return false otherwise.
   */
  public boolean isIntersecting(final Edge pq, int skew) {
    //Same line, no need to check
    if (this.equals(pq) || this.equals(pq.getReverse())) {
      return false;
    }
    //If they're parallel then check for overlapsed
    if (isParallel(pq)) {
      return isOverlap(pq);
    }

    //http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry2
    final double TOLERANCE = 0.0001;

    // A = y2 - y1
    double a1 = end.getY() - start.getY();
    double a2 = pq.getEnd().getY() - pq.getStart().getY();

    // B = x1 - x2
    double b1 = start.getX() - end.getX() + (skew * SKEW_DEG);
    double b2 = pq.getStart().getX() - pq.getEnd().getX();

    // C = A*x1 - B*y1
    double c1 = a1 * start.getX() + b1 * start.getY();
    double c2 = a2 * pq.getStart().getX() + b2 * pq.getStart().getY();

    double det = a1 * b2 - a2 * b1;

    // intersection point
    double x = (b2 * c1 - b1 * c2) / det;
    double y = (a1 * c2 - a2 * c1) / det;

    int minX1 = Math.min(start.getX(), end.getX());
    int minY1 = Math.min(start.getY(), end.getY());

    int maxX1 = Math.max(start.getX(), end.getX());
    int maxY1 = Math.max(start.getY(), end.getY());

    int minX2 = Math.min(pq.getStart().getX(), pq.getEnd().getX());
    int minY2 = Math.min(pq.getStart().getY(), pq.getEnd().getY());

    int maxX2 = Math.max(pq.getStart().getX(), pq.getEnd().getX());
    int maxY2 = Math.max(pq.getStart().getY(), pq.getEnd().getY());

    return ((minX1 <= x + TOLERANCE) && (x - TOLERANCE <= maxX1)
            && (minY1 <= y + TOLERANCE) && (y - TOLERANCE <= maxY1))
            && ((minX2 <= x + TOLERANCE) && (x - TOLERANCE <= maxX2)
            && (minY2 <= y + TOLERANCE) && (y - TOLERANCE <= maxY2));
  }

  public boolean isIntersecting(Vertex v) {
    double deltaX = (end.getX() - start.getX());
    if (deltaX == 0) { // slope is undefined
      int minY = Math.min(start.getY(), end.getY());
      int maxY = Math.max(start.getY(), end.getY());

      return start.getX() == v.getX()
              && (minY <= v.getY() && maxY >= v.getY());
    }


    double m = (end.getY() - start.getY()) / deltaX;
    if (m == 0) {
      int minX = Math.min(start.getX(), end.getX());
      int maxX = Math.max(start.getX(), end.getX());

      return start.getY() == v.getY()
              && (minX <= v.getX() && maxX >= v.getX());
    }

    // determine the intersection point from the slope
    double vY = v.getY();
    double b = ((double) start.getY()) - (m * ((double) start.getX())); // b = y - mx
    double edgeY = (m * v.getX()) + b;
    final double TOLERANCE = 0.001;
    return (edgeY - TOLERANCE) <= vY && vY <= (edgeY + TOLERANCE);
  }

  @Override
  public boolean equals(Object obj) {
    if (obj == null) {
      return false;
    }
    if (getClass() != obj.getClass()) {
      return false;
    }
    final Edge other = (Edge) obj;
    if (this.start != other.start && (this.start == null || !this.start.equals(other.start))) {
      return false;
    }
    if (this.end != other.end && (this.end == null || !this.end.equals(other.end))) {
      return false;
    }
    return true;
  }

  @Override
  public int hashCode() {
    int hash = 7;
    hash = 19 * hash + (this.start != null ? this.start.hashCode() : 0);
    hash = 19 * hash + (this.end != null ? this.end.hashCode() : 0);
    return hash;
  }

  // Utility functions. Not available to users of the class
  private boolean isOverlap(final Edge PQ) {
    //now that they're parallel, check whether or not they're really share any path
    if (PQ.start.equals(start) || PQ.end.equals(end)) //if they have same start or end point
    //return true if the two lines point into the same direction
    {
      return (end.getX() - start.getX()) * (PQ.end.getX() - PQ.start.getX()) > 0
              || (end.getY() - start.getY()) * (PQ.end.getY() - PQ.start.getY()) > 0;
    }
    if (PQ.start.equals(end) || PQ.end.equals(start)) //return true if the two lines point into oposite direction
    {
      return (end.getX() - start.getX()) * (PQ.end.getX() - PQ.start.getX()) < 0
              || (end.getY() - start.getY()) * (PQ.end.getY() - PQ.start.getY()) < 0;
    }
    return false;	//in case they're not share any point, they can't overlap.
  }

  private boolean isParallel(final Edge PQ) {
    return (end.getX() - start.getX()) * (PQ.end.getY() - PQ.start.getY())
            == (end.getY() - start.getY()) * (PQ.end.getX() - PQ.start.getX());
  }
}
